package leetcode.map;

import java.util.LinkedList;

public class Lc994 {

    int[] X = {-1, 1, 0, 0};
    int[] Y = {0, 0, -1, 1};

    public int orangesRotting(int[][] grid) {

        LinkedList<int[]> queue = new LinkedList<>();
        int orangeCount = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 0) {
                    orangeCount++;
                    if (grid[i][j] == 2) {
                        queue.offer(new int[]{i, j});
                    }
                }
            }
        }
        if (orangeCount == 0)
            return 0;
        int ans = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            orangeCount -= size;
            while (size-- > 0) {
                int[] pos = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = pos[0] + X[i];
                    int ny = pos[1] + Y[i];
                    if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            ans++;
        }
        return orangeCount == 0 ? ans : -1;
    }
}
